SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Randomized algorithm</title>

</head>

Randomized algorithm

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1246091330">

/* start https://en.wikipedia.org/ */

.mw-parser-output .sidebar{width:22em;float:right;clear:right;margin:0.5em 0 1em 1em;background:var(--background-color-neutral-subtle,#f8f9fa);border:1px solid var(--border-color-base,#a2a9b1);padding:0.2em;text-align:center;line-height:1.4em;font-size:88%;border-collapse:collapse;display:table}body.skin-minerva .mw-parser-output .sidebar{display:table!important;float:right!important;margin:0.5em 0 1em 1em!important}.mw-parser-output .sidebar-subgroup{width:100%;margin:0;border-spacing:0}.mw-parser-output .sidebar-left{float:left;clear:left;margin:0.5em 1em 1em 0}.mw-parser-output .sidebar-none{float:none;clear:both;margin:0.5em 1em 1em 0}.mw-parser-output .sidebar-outer-title{padding:0 0.4em 0.2em;font-size:125%;line-height:1.2em;font-weight:bold}.mw-parser-output .sidebar-top-image{padding:0.4em}.mw-parser-output .sidebar-top-caption,.mw-parser-output .sidebar-pretitle-with-top-image,.mw-parser-output .sidebar-caption{padding:0.2em 0.4em 0;line-height:1.2em}.mw-parser-output .sidebar-pretitle{padding:0.4em 0.4em 0;line-height:1.2em}.mw-parser-output .sidebar-title,.mw-parser-output .sidebar-title-with-pretitle{padding:0.2em 0.8em;font-size:145%;line-height:1.2em}.mw-parser-output .sidebar-title-with-pretitle{padding:0.1em 0.4em}.mw-parser-output .sidebar-image{padding:0.2em 0.4em 0.4em}.mw-parser-output .sidebar-heading{padding:0.1em 0.4em}.mw-parser-output .sidebar-content{padding:0 0.5em 0.4em}.mw-parser-output .sidebar-content-with-subgroup{padding:0.1em 0.4em 0.2em}.mw-parser-output .sidebar-above,.mw-parser-output .sidebar-below{padding:0.3em 0.8em;font-weight:bold}.mw-parser-output .sidebar-collapse .sidebar-above,.mw-parser-output .sidebar-collapse .sidebar-below{border-top:1px solid #aaa;border-bottom:1px solid #aaa}.mw-parser-output .sidebar-navbar{text-align:right;font-size:115%;padding:0 0.4em 0.4em}.mw-parser-output .sidebar-list-title{padding:0 0.4em;text-align:left;font-weight:bold;line-height:1.6em;font-size:105%}.mw-parser-output .sidebar-list-title-c{padding:0 0.4em;text-align:center;margin:0 3.3em}@media(max-width:640px){body.mediawiki .mw-parser-output .sidebar{width:100%!important;clear:both;float:none!important;margin-left:0!important;margin-right:0!important}}body.skin--responsive .mw-parser-output .sidebar a>img{max-width:none!important}@media screen{html.skin-theme-clientpref-night .mw-parser-output .sidebar:not(.notheme) .sidebar-list-title,html.skin-theme-clientpref-night .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle{background:transparent!important}html.skin-theme-clientpref-night .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle a{color:var(--color-progressive)!important}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .sidebar:not(.notheme) .sidebar-list-title,html.skin-theme-clientpref-os .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle{background:transparent!important}html.skin-theme-clientpref-os .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle a{color:var(--color-progressive)!important}}@media print{body.ns-0 .mw-parser-output .sidebar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><table class="sidebar nomobile nowraplinks"><tbody><tr><td class="sidebar-pretitle">Part of a series on</td></tr><tr><th class="sidebar-title-with-pretitle" style="background:#ccccff;"> <a href="Data_structure" title="Data structure">data structures</a></th></tr><tr><td class="sidebar-content hlist">

<ul><li><a href="Bloom_filter" title="Bloom filter">Bloom filter</a></li>

<li><a href="Count_sketch" title="Count sketch">Count sketch</a></li>

<li><a href="Count%E2%80%93min_sketch" title="Count–min sketch">Count–min sketch</a></li>

<li><a href="Quotient_filter" title="Quotient filter">Quotient filter</a></li>

</tr><tr><th class="sidebar-heading" style="background:#ddddff;">

<a href="Random_tree" title="Random tree">Random trees</a></th></tr><tr><td class="sidebar-content hlist">

<ul><li><a href="Random_binary_tree" title="Random binary tree">Random binary tree</a></li>

<li><a href="Treap" title="Treap">Treap</a></li>

<li><a href="Rapidly_exploring_random_tree" title="Rapidly exploring random tree">Rapidly exploring random tree</a></li></ul></td>

</tr><tr><th class="sidebar-heading" style="background:#ddddff;">

Related</th></tr><tr><td class="sidebar-content hlist">

<ul>

<li><a href="HyperLogLog" title="HyperLogLog">HyperLogLog</a></li></ul></td>

</tr><tr><td class="sidebar-navbar"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></td></tr></tbody></table>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">"Randomized algorithms" redirects here; not to be confused with <a href="Algorithmic_randomness" class="mw-redirect" title="Algorithmic randomness">Algorithmic randomness</a>.</div>

A randomized algorithm is an <a href="Algorithm" title="Algorithm">algorithm</a> that employs a degree of <a href="Randomness" title="Randomness">randomness</a> as part of its logic or procedure. The algorithm typically uses <a href="Uniform_distribution_(discrete)" class="mw-redirect" title="Uniform distribution (discrete)">uniformly random</a> bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the "average case" over all possible choices of random determined by the random bits; thus either the running time, or the output (or both) are random variables.

There is a distinction between algorithms that use the random input so that they always terminate with the correct answer, but where the expected running time is finite (<a href="Las_Vegas_algorithm" title="Las Vegas algorithm">Las Vegas algorithms</a>, for example <a href="Quicksort" title="Quicksort">Quicksort</a><a href="#cite_note-1">[1]</a>), and algorithms which have a chance of producing an incorrect result (<a href="Monte_Carlo_algorithm" title="Monte Carlo algorithm">Monte Carlo algorithms</a>, for example the Monte Carlo algorithm for the <a href="Minimum_feedback_arc_set" class="mw-redirect" title="Minimum feedback arc set">MFAS</a> problem<a href="#cite_note-2">[2]</a>) or fail to produce a result either by signaling a failure or failing to terminate. In some cases, probabilistic algorithms are the only practical means of solving a problem.<a href="#cite_note-3">[3]</a>

In common practice, randomized algorithms are approximated using a <a href="Pseudorandom_number_generator" title="Pseudorandom number generator">pseudorandom number generator</a> in place of a true source of random bits; such an implementation may deviate from the expected theoretical behavior and mathematical guarantees which may depend on the existence of an ideal true random number generator.

<div class="mw-heading mw-heading2"><h2 id="Motivation">Motivation</h2></div>

As a motivating example, consider the problem of finding an ‘a’ in an <a href="Array_data_structure" class="mw-redirect" title="Array data structure">array</a> of n elements.

Input: An array of n≥2 elements, in which half are ‘a’s and the other half are ‘b’s.

Output: Find an ‘a’ in the array.

We give two versions of the algorithm, one <a href="Las_Vegas_algorithm" title="Las Vegas algorithm">Las Vegas algorithm</a> and one <a href="Monte_Carlo_algorithm" title="Monte Carlo algorithm">Monte Carlo algorithm</a>.

Las Vegas algorithm:

<div class="mw-highlight mw-highlight-lang-pascal mw-content-ltr" dir="ltr"><pre>findingA_LV(array A, n)

begin

repeat

Randomly select one element out of n elements.

until 'a' is found

end

</pre></div>

This algorithm succeeds with probability 1. The number of iterations varies and can be arbitrarily large, but the expected number of iterations is

</mrow>

</munder>

</mrow>

</mrow>

</munderover>

<mfrac>

<msup>

</mrow>

</msup>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lim _{n\to \infty }\sum _{i=1}^{n}{\frac {i}{2^{i}}}=2}</annotation>

</semantics>

</math><img src="./28b23b9a9c100091938f875a021b7691086adeec.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:15.461ex; height:6.843ex;" alt="{\displaystyle \lim _{n\to \infty }\sum _{i=1}^{n}{\frac {i}{2^{i}}}=2}" loading="lazy"></dd></dl>

Since it is constant, the expected run time over many calls is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Theta (1)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (1)}</annotation>

</semantics>

</math><img src="./fb3ae2cd10dbd21019bb13c462144f1bdc030e49.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.78ex; height:2.843ex;" alt="{\displaystyle \Theta (1)}" loading="lazy">. (See <a href="Big_Theta_notation" class="mw-redirect" title="Big Theta notation">Big Theta notation</a>)

Monte Carlo algorithm:

<div class="mw-highlight mw-highlight-lang-pascal mw-content-ltr" dir="ltr"><pre>findingA_MC(array A, n, k)

begin

i := 0

repeat

i := i + 1

until i = k or 'a' is found

end

</pre></div>

If an ‘a’ is found, the algorithm succeeds, else the algorithm fails. After k iterations, the probability of finding an ‘a’ is:

</mrow>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Pr[\mathrm {find~a} ]=1-(1/2)^{k}}</annotation>

</semantics>

</math><img src="./2c3fa724b0da3c3ac125350c4d0703329e0eabbc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:23.115ex; height:3.176ex;" alt="{\displaystyle \Pr[\mathrm {find~a} ]=1-(1/2)^{k}}" loading="lazy">

</div>

This algorithm does not guarantee success, but the run time is bounded. The number of iterations is always less than or equal to k. Taking k to be constant the run time (expected and absolute) is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Theta (1)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (1)}</annotation>

</semantics>

Randomized algorithms are particularly useful when faced with a malicious "adversary" or <a href="Attacker" title="Attacker">attacker</a> who deliberately tries to feed a bad input to the algorithm (see <a href="Worst-case_complexity" title="Worst-case complexity">worst-case complexity</a> and <a href="Competitive_analysis_(online_algorithm)" title="Competitive analysis (online algorithm)">competitive analysis (online algorithm)</a>) such as in the <a href="Prisoner's_dilemma" title="Prisoner's dilemma">Prisoner's dilemma</a>. It is for this reason that <a href="Randomness" title="Randomness">randomness</a> is ubiquitous in <a href="Cryptography" title="Cryptography">cryptography</a>. In cryptographic applications, pseudo-random numbers cannot be used, since the adversary can predict them, making the algorithm effectively deterministic. Therefore, either a source of truly random numbers or a <a href="Cryptographically_secure_pseudo-random_number_generator" class="mw-redirect" title="Cryptographically secure pseudo-random number generator">cryptographically secure pseudo-random number generator</a> is required. Another area in which randomness is inherent is <a href="Quantum_computer" class="mw-redirect" title="Quantum computer">quantum computing</a>.

In the example above, the Las Vegas algorithm always outputs the correct answer, but its running time is a random variable. The Monte Carlo algorithm (related to the <a href="Monte_Carlo_method" title="Monte Carlo method">Monte Carlo method</a> for simulation) is guaranteed to complete in an amount of time that can be bounded by a function the input size and its parameter k, but allows a small probability of error. Observe that any Las Vegas algorithm can be converted into a Monte Carlo algorithm (via <a href="Markov's_inequality" title="Markov's inequality">Markov's inequality</a>), by having it output an arbitrary, possibly incorrect answer if it fails to complete within a specified time. Conversely, if an efficient verification procedure exists to check whether an answer is correct, then a Monte Carlo algorithm can be converted into a Las Vegas algorithm by running the Monte Carlo algorithm repeatedly till a correct answer is obtained.

<div class="mw-heading mw-heading2"><h2 id="Computational_complexity">Computational complexity</h2></div>

<a href="Computational_complexity_theory" title="Computational complexity theory">Computational complexity theory</a> models randomized algorithms as <a href="Probabilistic_Turing_machine" title="Probabilistic Turing machine">probabilistic Turing machines</a>. Both <a href="Las_Vegas_algorithm" title="Las Vegas algorithm">Las Vegas</a> and <a href="Monte_Carlo_algorithm" title="Monte Carlo algorithm">Monte Carlo algorithms</a> are considered, and several <a href="Complexity_class" title="Complexity class">complexity classes</a> are studied. The most basic randomized complexity class is <a href="RP_(complexity)" title="RP (complexity)">RP</a>, which is the class of <a href="Decision_problem" title="Decision problem">decision problems</a> for which there is an efficient (polynomial time) randomized algorithm (or probabilistic Turing machine) which recognizes NO-instances with absolute certainty and recognizes YES-instances with a probability of at least 1/2. The complement class for RP is co-RP. Problem classes having (possibly nonterminating) algorithms with <a href="Polynomial_time" class="mw-redirect" title="Polynomial time">polynomial time</a> average case running time whose output is always correct are said to be in <a href="ZPP_(complexity)" title="ZPP (complexity)">ZPP</a>.

The class of problems for which both YES and NO-instances are allowed to be identified with some error is called <a href="Bounded-error_probabilistic_polynomial" class="mw-redirect" title="Bounded-error probabilistic polynomial">BPP</a>. This class acts as the randomized equivalent of <a href="P_(complexity)" title="P (complexity)">P</a>, i.e. BPP represents the class of efficient randomized algorithms.

<div class="mw-heading mw-heading2"><h2 id="Early_history">Early history</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Sorting">Sorting</h3></div>

<a href="Quicksort" title="Quicksort">Quicksort</a> was discovered by <a href="Tony_Hoare" title="Tony Hoare">Tony Hoare</a> in 1959, and subsequently published in 1961.<a href="#cite_note-4">[4]</a> In the same year, Hoare published the <a href="Quickselect" title="Quickselect">quickselect algorithm</a>,<a href="#cite_note-5">[5]</a> which finds the median element of a list in linear expected time. It remained open until 1973 whether a deterministic linear-time algorithm existed.<a href="#cite_note-6">[6]</a>

<div class="mw-heading mw-heading3"><h3 id="Number_theory">Number theory</h3></div>

In 1917, <a href="Henry_Cabourn_Pocklington" title="Henry Cabourn Pocklington">Henry Cabourn Pocklington</a> introduced a randomized algorithm known as <a href="Pocklington's_algorithm" title="Pocklington's algorithm">Pocklington's algorithm</a> for efficiently finding <a href="Square_root" title="Square root">square roots</a> modulo prime numbers.<a href="#cite_note-7">[7]</a>

In 1970, <a href="Elwyn_Berlekamp" title="Elwyn Berlekamp">Elwyn Berlekamp</a> introduced a randomized algorithm for efficiently computing the roots of a polynomial over a finite field.<a href="#cite_note-8">[8]</a> In 1977, <a href="Robert_M._Solovay" title="Robert M. Solovay">Robert M. Solovay</a> and <a href="Volker_Strassen" title="Volker Strassen">Volker Strassen</a> discovered a polynomial-time <a href="Solovay%E2%80%93Strassen_primality_test" title="Solovay–Strassen primality test">randomized primality test</a> (i.e., determining the <a href="Primality_test" title="Primality test">primality</a> of a number). Soon afterwards <a href="Michael_O._Rabin" title="Michael O. Rabin">Michael O. Rabin</a> demonstrated that the 1976 <a href="Miller%E2%80%93Rabin_primality_test" title="Miller–Rabin primality test">Miller's primality test</a> could also be turned into a polynomial-time randomized algorithm. At that time, no provably polynomial-time <a href="Deterministic_algorithm" title="Deterministic algorithm">deterministic algorithms</a> for primality testing were known.

<div class="mw-heading mw-heading3"><h3 id="Data_structures">Data structures</h3></div>

One of the earliest randomized data structures is the <a href="Hash_table" title="Hash table">hash table</a>, which was introduced in 1953 by <a href="Hans_Peter_Luhn" title="Hans Peter Luhn">Hans Peter Luhn</a> at <a href="IBM" title="IBM">IBM</a>.<a href="#cite_note-:0-9">[9]</a> Luhn's hash table used chaining to resolve collisions and was also one of the first applications of <a href="Linked_list" title="Linked list">linked lists</a>.<a href="#cite_note-:0-9">[9]</a> Subsequently, in 1954, <a href="Gene_Amdahl" title="Gene Amdahl">Gene Amdahl</a>, <a href="Elaine_M._McGraw" title="Elaine M. McGraw">Elaine M. McGraw</a>, <a href="Nathaniel_Rochester_(computer_scientist)" title="Nathaniel Rochester (computer scientist)">Nathaniel Rochester</a>, and <a href="Arthur_Samuel_(computer_scientist)" title="Arthur Samuel (computer scientist)">Arthur Samuel</a> of <a href="IBM_Research" title="IBM Research">IBM Research</a> introduced <a href="Linear_probing" title="Linear probing">linear probing</a>,<a href="#cite_note-:0-9">[9]</a> although <a href="Andrey_Ershov" class="mw-redirect" title="Andrey Ershov">Andrey Ershov</a> independently had the same idea in 1957.<a href="#cite_note-:0-9">[9]</a> In 1962, <a href="Donald_Knuth" title="Donald Knuth">Donald Knuth</a> performed the first correct analysis of linear probing,<a href="#cite_note-:0-9">[9]</a> although the memorandum containing his analysis was not published until much later.<a href="#cite_note-10">[10]</a> The first published analysis was due to Konheim and Weiss in 1966.<a href="#cite_note-11">[11]</a>

Early works on hash tables either assumed access to a fully random hash function or assumed that the keys themselves were random.<a href="#cite_note-:0-9">[9]</a> In 1979, Carter and Wegman introduced <a href="Universal_hashing" title="Universal hashing">universal hash functions</a>,<a href="#cite_note-12">[12]</a> which they showed could be used to implement chained hash tables with constant expected time per operation.

Early work on randomized data structures also extended beyond hash tables. In 1970, Burton Howard Bloom introduced an approximate-membership data structure known as the <a href="Bloom_filter" title="Bloom filter">Bloom filter</a>.<a href="#cite_note-13">[13]</a> In 1989, <a href="Raimund_Seidel" title="Raimund Seidel">Raimund Seidel</a> and <a href="Cecilia_R._Aragon" title="Cecilia R. Aragon">Cecilia R. Aragon</a> introduced a randomized balanced search tree known as the <a href="Treap" title="Treap">treap</a>.<a href="#cite_note-14">[14]</a> In the same year, <a href="William_Pugh_(computer_scientist)" title="William Pugh (computer scientist)">William Pugh</a> introduced another randomized search tree known as the <a href="Skip_list" title="Skip list">skip list</a>.<a href="#cite_note-15">[15]</a>

<div class="mw-heading mw-heading3"><h3 id="Implicit_uses_in_combinatorics">Implicit uses in combinatorics</h3></div>

Prior to the popularization of randomized algorithms in computer science, <a href="Paul_Erd%C5%91s" title="Paul Erdős">Paul Erdős</a> popularized the use of randomized constructions as a mathematical technique for establishing the existence of mathematical objects. This technique has become known as the <a href="Probabilistic_method" title="Probabilistic method">probabilistic method</a>.<a href="#cite_note-:1-16">[16]</a> <a href="Paul_Erd%C5%91s" title="Paul Erdős">Erdős</a> gave his first application of the probabilistic method in 1947, when he used a simple randomized construction to establish the existence of Ramsey graphs.<a href="#cite_note-17">[17]</a> He famously used a more sophisticated randomized algorithm in 1959 to establish the existence of graphs with high girth and chromatic number.<a href="#cite_note-18">[18]</a><a href="#cite_note-:1-16">[16]</a>

<div class="mw-heading mw-heading2"><h2 id="Examples">Examples</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Quicksort">Quicksort</h3></div>

<a href="Quicksort" title="Quicksort">Quicksort</a> is a familiar, commonly used algorithm in which randomness can be useful. Many deterministic versions of this algorithm require <a href="Big_O_notation" title="Big O notation">O</a>(n2) time to sort n numbers for some well-defined class of degenerate inputs (such as an already sorted array), with the specific class of inputs that generate this behavior defined by the protocol for pivot selection. However, if the algorithm selects pivot elements uniformly at random, it has a provably high probability of finishing in O(n log n) time regardless of the characteristics of the input.

<div class="mw-heading mw-heading3"><h3 id="Randomized_incremental_constructions_in_geometry">Randomized incremental constructions in geometry</h3></div>

In <a href="Computational_geometry" title="Computational geometry">computational geometry</a>, a standard technique to build a structure like a <a href="Convex_hull" title="Convex hull">convex hull</a> or <a href="Delaunay_triangulation" title="Delaunay triangulation">Delaunay triangulation</a> is to randomly permute the input points and then insert them one by one into the existing structure. The randomization ensures that the expected number of changes to the structure caused by an insertion is small, and so the expected running time of the algorithm can be bounded from above. This technique is known as randomized incremental construction.<a href="#cite_note-19">[19]</a>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Karger's_algorithm" title="Karger's algorithm">Karger's algorithm</a></div>

Input: A <a href="Graph_theory" title="Graph theory">graph</a> G(V,E)

Output: A <a href="Cut_(graph_theory)" title="Cut (graph theory)">cut</a> partitioning the vertices into L and R, with the minimum number of edges between L and R.

Recall that the <a href="Edge_contraction" title="Edge contraction">contraction</a> of two nodes, u and v, in a (multi-)graph yields a new node u ' with edges that are the union of the edges incident on either u or v, except from any edge(s) connecting u and v. Figure 1 gives an example of contraction of vertex A and B.

After contraction, the resulting graph may have parallel edges, but contains no self loops.

Karger's<a href="#cite_note-20">[20]</a> basic algorithm:

<pre>begin

i = 1

repeat

Take a random edge (u,v) ∈ E in G

replace u and v with the contraction u'

until only 2 nodes remain

obtain the corresponding cut result Ci

i = i + 1

until i = m

output the minimum cut among C1, C2, ..., Cm.

end

</pre>

In each execution of the outer loop, the algorithm repeats the inner loop until only 2 nodes remain, the corresponding cut is obtained. The run time of one execution is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n)}</annotation>

</semantics>

</math><img src="./34109fe397fdcff370079185bfdb65826cb5565a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.977ex; height:2.843ex;" alt="{\displaystyle O(n)}" loading="lazy">, and n denotes the number of vertices.

After m times executions of the outer loop, we output the minimum cut among all the results. The figure 2 gives an

example of one execution of the algorithm. After execution, we get a cut of size 3.

/* start https://en.wikipedia.org/ */

.mw-parser-output .math_theorem{margin:1em 2em;padding:0.5em 1em 0.4em;border:1px solid #aaa;overflow:hidden}@media(max-width:500px){.mw-parser-output .math_theorem{margin:1em 0em;padding:0.5em 0.5em 0.4em}}

/* end https://en.wikipedia.org/ */

</style><div class="math_theorem" style="">

Lemma 1—Let k be the min cut size, and let C = {e1, e2, ..., ek} be the min cut. If, during iteration i, no edge e ∈ C is selected for contraction, then Ci = C.

</div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .math_proof{border:thin solid #aaa;margin:1em 2em;padding:0.5em 1em 0.4em}@media(max-width:500px){.mw-parser-output .math_proof{margin:1em 0;padding:0.5em 0.5em 0.4em}}

/* end https://en.wikipedia.org/ */

</style><div class="math_proof" style="">Proof

If G is not connected, then G can be partitioned into L and R without any edge between them. So the min cut in a disconnected graph is 0. Now, assume G is connected. Let V=L∪R be the partition of V induced by C : C = { {u,v} ∈ E : u ∈ L,v ∈ R} (well-defined since G is connected). Consider an edge {u,v} of C. Initially, u,v are distinct vertices. As long as we pick an edge ⁠<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f\neq e}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f\neq e}</annotation>

</semantics>

</math><img src="./e06e0616cd0985f8f2254ec0a651213b4e1a159d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.461ex; height:2.676ex;" alt="{\displaystyle f\neq e}" loading="lazy">⁠, u and v do not get merged. Thus, at the end of the algorithm, we have two compound nodes covering the entire graph, one consisting of the vertices of L and the other consisting of the vertices of R. As in figure 2, the size of min cut is 1, and C = {(A,B)}. If we don't select (A,B) for contraction, we can get the min cut.

</div>

Lemma 2—If G is a multigraph with p vertices and whose min cut has size k, then G has at least pk/2 edges.

</div>

<div class="math_proof" style="">Proof

Because the min cut is k, every vertex v must satisfy degree(v) ≥ k. Therefore, the sum of the degree is at least pk. But it is well known that the sum of vertex degrees equals 2|E|. The lemma follows.

</div>

<div class="mw-heading mw-heading4"><h4 id="Analysis_of_algorithm">Analysis of algorithm</h4></div>

The probability that the algorithm succeeds is 1 − the probability that all attempts fail. By independence, the probability that all attempts fail is

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \prod _{i=1}^{m}\Pr(C_{i}\neq C)=\prod _{i=1}^{m}(1-\Pr(C_{i}=C)).}</annotation>

</semantics>

</math>

By lemma 1, the probability that Ci = C is the probability that no edge of C is selected during iteration i. Consider the inner loop and let Gj denote the graph after j edge contractions, where j ∈ {0, 1, …, n − 3}. Gj has n − j vertices. We use the chain rule of <a href="Conditional_probability" title="Conditional probability">conditional possibilities</a>.

The probability that the edge chosen at iteration j is not in C, given that no edge of C has been chosen before, is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1-{\frac {k}{|E(G_{j})|}}}">

<mfrac>

<mrow>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1-{\frac {k}{|E(G_{j})|}}}</annotation>

</semantics>

</math><img src="./ef9c91c421134a1e01d64a4f8937e1895aadc59f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:12.454ex; height:6.176ex;" alt="{\displaystyle 1-{\frac {k}{|E(G_{j})|}}}" loading="lazy">. Note that Gj still has min cut of size k, so by Lemma 2, it still has at least <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {(n-j)k}{2}}}">

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {(n-j)k}{2}}}</annotation>

</semantics>

</math><img src="./50518ee4af22931cb0bde886fc34cb2a048e271c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:9.05ex; height:5.676ex;" alt="{\displaystyle {\frac {(n-j)k}{2}}}" loading="lazy"> edges.

Thus, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1-{\frac {k}{|E(G_{j})|}}\geq 1-{\frac {2}{n-j}}={\frac {n-j-2}{n-j}}}">

<mfrac>

<mrow>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

<mfrac>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1-{\frac {k}{|E(G_{j})|}}\geq 1-{\frac {2}{n-j}}={\frac {n-j-2}{n-j}}}</annotation>

</semantics>

</math><img src="./d66862f86b105833468ab3619994021555dd8081.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:38.715ex; height:6.176ex;" alt="{\displaystyle 1-{\frac {k}{|E(G_{j})|}}\geq 1-{\frac {2}{n-j}}={\frac {n-j-2}{n-j}}}" loading="lazy">.

So by the chain rule, the probability of finding the min cut C is

<msub>

</mrow>

</msub>

<mrow>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

<mrow>

<mfrac>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

<mrow>

<mfrac>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Pr[C_{i}=C]\geq \left({\frac {n-2}{n}}\right)\left({\frac {n-3}{n-1}}\right)\left({\frac {n-4}{n-2}}\right)\ldots \left({\frac {3}{5}}\right)\left({\frac {2}{4}}\right)\left({\frac {1}{3}}\right).}</annotation>

</semantics>

</math>

Cancellation gives <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Pr[C_{i}=C]\geq {\frac {2}{n(n-1)}}}">

<msub>

</mrow>

</msub>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Pr[C_{i}=C]\geq {\frac {2}{n(n-1)}}}</annotation>

</semantics>

</math><img src="./f9a5ee0a8aef637a2522ae343d168d48bb739389.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:23.651ex; height:6.009ex;" alt="{\displaystyle \Pr[C_{i}=C]\geq {\frac {2}{n(n-1)}}}" loading="lazy">. Thus the probability that the algorithm succeeds is at least <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1-\left(1-{\frac {2}{n(n-1)}}\right)^{m}}">

<msup>

<mrow>

<mrow>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1-\left(1-{\frac {2}{n(n-1)}}\right)^{m}}</annotation>

</semantics>

</math><img src="./619ace45ff61354cc374c7ce6be9ae79fafff277.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:22.54ex; height:6.343ex;" alt="{\displaystyle 1-\left(1-{\frac {2}{n(n-1)}}\right)^{m}}" loading="lazy">. For <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m={\frac {n(n-1)}{2}}\ln n}">

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m={\frac {n(n-1)}{2}}\ln n}</annotation>

</semantics>

</math><img src="./193a8af166ca8c7f076040adb4d6b7d255392fb9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:18.685ex; height:5.676ex;" alt="{\displaystyle m={\frac {n(n-1)}{2}}\ln n}" loading="lazy">, this is equivalent to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1-{\frac {1}{n}}}">

<mfrac>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1-{\frac {1}{n}}}</annotation>

</semantics>

</math><img src="./2aa9ee64f95306042fd5ae4367891eb1a0d72cc1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:6.234ex; height:5.176ex;" alt="{\displaystyle 1-{\frac {1}{n}}}" loading="lazy">. The algorithm finds the min cut with probability <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1-{\frac {1}{n}}}">

<mfrac>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1-{\frac {1}{n}}}</annotation>

</semantics>

</math><img src="./2aa9ee64f95306042fd5ae4367891eb1a0d72cc1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:6.234ex; height:5.176ex;" alt="{\displaystyle 1-{\frac {1}{n}}}" loading="lazy">, in time <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(mn)=O(n^{3}\log n)}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(mn)=O(n^{3}\log n)}</annotation>

</semantics>

</math><img src="./0545706ab60a6ab301cf83adf20f578d60f7f628.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.288ex; height:3.176ex;" alt="{\displaystyle O(mn)=O(n^{3}\log n)}" loading="lazy">.

<div class="mw-heading mw-heading2"><h2 id="Derandomization">Derandomization</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

Randomness can be viewed as a resource, like space and time. Derandomization is then the process of removing randomness (or using as little of it as possible).<a href="#cite_note-21">[21]</a><a href="#cite_note-22">[22]</a> It is not currently known if all algorithms can be derandomized without significantly increasing their running time.<a href="#cite_note-:2-23">[23]</a> For instance, in <a href="Analysis_of_algorithms" title="Analysis of algorithms">computational complexity</a>, it is unknown whether <a href="P_(complexity)" title="P (complexity)">P</a> = <a href="Bounded-error_probabilistic_polynomial" class="mw-redirect" title="Bounded-error probabilistic polynomial">BPP</a>,<a href="#cite_note-:2-23">[23]</a> i.e., we do not know whether we can take an arbitrary randomized algorithm that runs in polynomial time with a small error probability and derandomize it to run in polynomial time without using randomness.

There are specific methods that can be employed to derandomize particular randomized algorithms:

<ul><li>the <a href="Method_of_conditional_probabilities" title="Method of conditional probabilities">method of conditional probabilities</a>, and its generalization, <a href="Pessimistic_estimator" class="mw-redirect" title="Pessimistic estimator">pessimistic estimators</a></li>

<li><a href="Discrepancy_theory" title="Discrepancy theory">discrepancy theory</a> (which is used to derandomize geometric algorithms)</li>

<li>the exploitation of limited independence in the random variables used by the algorithm, such as the <a href="Pairwise_independence" title="Pairwise independence">pairwise independence</a> used in <a href="Universal_hashing" title="Universal hashing">universal hashing</a><a href="#cite_note-24">[24]</a></li>

<li>the use of <a href="Expander_graph" title="Expander graph">expander graphs</a> (or <a href="Disperser" title="Disperser">dispersers</a> in general) to amplify a limited amount of initial randomness (this last approach is also referred to as generating <a href="Pseudorandom" class="mw-redirect" title="Pseudorandom">pseudorandom</a> bits from a random source, and leads to the related topic of pseudorandomness)</li>

<li>changing the randomized algorithm to use a <a href="Hash_function" title="Hash function">hash function</a> as a source of randomness for the algorithm's tasks, and then derandomizing the algorithm by <a href="Brute-force_search" title="Brute-force search">brute-forcing</a> all possible parameters (seeds) of the hash function. This technique is usually used to exhaustively search a sample space and making the algorithm deterministic (e.g. randomized graph algorithms)</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Where_randomness_helps">Where randomness helps</h2></div>

When the model of computation is restricted to <a href="Turing_machine" title="Turing machine">Turing machines</a>, it is currently an open question whether the ability to make random choices allows some problems to be solved in polynomial time that cannot be solved in polynomial time without this ability; this is the question of whether P = BPP. However, in other contexts, there are specific examples of problems where randomization yields strict improvements.

<ul><li>Based on the initial motivating example: given an exponentially long string of 2k characters, half a's and half b's, a <a href="Random-access_machine" title="Random-access machine">random-access machine</a> requires 2k−1 lookups in the worst-case to find the index of an a; if it is permitted to make random choices, it can solve this problem in an expected polynomial number of lookups.</li>

<li>The natural way of carrying out a numerical computation in <a href="Embedded_systems" class="mw-redirect" title="Embedded systems">embedded systems</a> or <a href="Cyber-physical_system" title="Cyber-physical system">cyber-physical systems</a> is to provide a result that approximates the correct one with high probability (or Probably Approximately Correct Computation (PACC)). The hard problem associated with the evaluation of the discrepancy loss between the approximated and the correct computation can be effectively addressed by resorting to randomization<a href="#cite_note-25">[25]</a></li>

<li>In <a href="Communication_complexity" title="Communication complexity">communication complexity</a>, the equality of two strings can be verified to some reliability using <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \log n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \log n}</annotation>

</semantics>

</math><img src="./317ab5292da7c7935aec01a570461fe0613b21d5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.754ex; height:2.509ex;" alt="{\displaystyle \log n}" loading="lazy"> bits of communication with a randomized protocol. Any deterministic protocol requires <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Theta (n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (n)}</annotation>

</semantics>

</math><img src="./a6351206e27071559aa4472579095994f650d76b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.012ex; height:2.843ex;" alt="{\displaystyle \Theta (n)}" loading="lazy"> bits if defending against a strong opponent.<a href="#cite_note-26">[26]</a></li>

<li>The volume of a convex body can be estimated by a randomized algorithm to arbitrary precision in polynomial time.<a href="#cite_note-27">[27]</a> <a href="Imre_B%C3%A1r%C3%A1ny" title="Imre Bárány">Bárány</a> and <a href="Zolt%C3%A1n_F%C3%BCredi" title="Zoltán Füredi">Füredi</a> showed that no deterministic algorithm can do the same.<a href="#cite_note-28">[28]</a> This is true unconditionally, i.e. without relying on any complexity-theoretic assumptions, assuming the convex body can be queried only as a black box.</li>

<li>A more complexity-theoretic example of a place where randomness appears to help is the class <a href="IP_(complexity)" title="IP (complexity)">IP</a>. IP consists of all languages that can be accepted (with high probability) by a polynomially long interaction between an all-powerful prover and a verifier that implements a BPP algorithm. IP = <a href="PSPACE" title="PSPACE">PSPACE</a>.<a href="#cite_note-29">[29]</a> However, if it is required that the verifier be deterministic, then IP = <a href="NP_(complexity)" title="NP (complexity)">NP</a>.</li>

<li>In a <a href="Chemical_reaction_network" class="mw-redirect" title="Chemical reaction network">chemical reaction network</a> (a finite set of reactions like A+B → 2C + D operating on a finite number of molecules), the ability to ever reach a given target state from an initial state is decidable, while even approximating the probability of ever reaching a given target state (using the standard concentration-based probability for which reaction will occur next) is undecidable. More specifically, a limited Turing machine can be simulated with arbitrarily high probability of running correctly for all time, only if a random chemical reaction network is used. With a simple nondeterministic chemical reaction network (any possible reaction can happen next), the computational power is limited to <a href="Primitive_recursive" class="mw-redirect" title="Primitive recursive">primitive recursive functions</a>.<a href="#cite_note-30">[30]</a></li></ul>

<ul><li><a href="Approximate_counting_algorithm" title="Approximate counting algorithm">Approximate counting algorithm</a></li>

<li><a href="Atlantic_City_algorithm" title="Atlantic City algorithm">Atlantic City algorithm</a></li>

<li><a href="Bogosort" title="Bogosort">Bogosort</a></li>

<li><a href="Count%E2%80%93min_sketch" title="Count–min sketch">Count–min sketch</a></li>

<li><a href="HyperLogLog" title="HyperLogLog">HyperLogLog</a></li>

<li><a href="Karger's_algorithm" title="Karger's algorithm">Karger's algorithm</a></li>

<li><a href="Las_Vegas_algorithm" title="Las Vegas algorithm">Las Vegas algorithm</a></li>

<li><a href="Monte_Carlo_algorithm" title="Monte Carlo algorithm">Monte Carlo algorithm</a></li>

<li><a href="Principle_of_deferred_decision" title="Principle of deferred decision">Principle of deferred decision</a></li>

<li><a href="Probabilistic_analysis_of_algorithms" title="Probabilistic analysis of algorithms">Probabilistic analysis of algorithms</a></li>

<li><a href="Probabilistic_roadmap" title="Probabilistic roadmap">Probabilistic roadmap</a></li>

<li><a href="Randomized_algorithms_as_zero-sum_games" class="mw-redirect" title="Randomized algorithms as zero-sum games">Randomized algorithms as zero-sum games</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFHoare1961" class="citation journal cs1">Hoare, C. A. R. (July 1961). "Algorithm 64: Quicksort". Commun. ACM. 4 (7): 321–. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F366622.366644">10.1145/366622.366644</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0001-0782">0001-0782</a>.</cite>

</li>

<li id="cite_note-2"><a href="#cite_ref-2">^</a> <cite id="CITEREFKudelić2016" class="citation journal cs1">Kudelić, Robert (2016-04-01). "Monte-Carlo randomized algorithm for minimal feedback arc set problem". Applied Soft Computing. 41: 235–246. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.asoc.2015.12.018">10.1016/j.asoc.2015.12.018</a>.</cite>

</li>

<li id="cite_note-3"><a href="#cite_ref-3">^</a> "In <a href="Primality_test" title="Primality test">testing primality</a> of very large numbers chosen at random, the chance of stumbling upon a value that fools the <a href="Fermat_primality_test" title="Fermat primality test">Fermat test</a> is less than the chance that <a href="Cosmic_radiation" class="mw-redirect" title="Cosmic radiation">cosmic radiation</a> will cause the computer to make an error in carrying out a 'correct' algorithm. Considering an algorithm to be inadequate for the first reason but not for the second illustrates the difference between mathematics and engineering." <a href="Hal_Abelson" title="Hal Abelson">Hal Abelson</a> and <a href="Gerald_J._Sussman" class="mw-redirect" title="Gerald J. Sussman">Gerald J. Sussman</a> (1996). <a href="Structure_and_Interpretation_of_Computer_Programs" title="Structure and Interpretation of Computer Programs">Structure and Interpretation of Computer Programs</a>. <a href="MIT_Press" title="MIT Press">MIT Press</a>, <a rel="nofollow" class="external text" href="http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#footnote_Temp_80">section 1.2</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20060903155101/http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#footnote_Temp_80">Archived</a> 2006-09-03 at the <a href="Wayback_Machine" title="Wayback Machine">Wayback Machine</a>.

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a> <cite id="CITEREFHoare1961" class="citation journal cs1">Hoare, C. A. R. (July 1961). <a rel="nofollow" class="external text" href="https://dl.acm.org/doi/10.1145/366622.366644">"Algorithm 64: Quicksort"</a>. Communications of the ACM. 4 (7): 321. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F366622.366644">10.1145/366622.366644</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0001-0782">0001-0782</a>.</cite>

</li>

<li id="cite_note-5"><a href="#cite_ref-5">^</a> <cite id="CITEREFHoare1961" class="citation journal cs1">Hoare, C. A. R. (July 1961). <a rel="nofollow" class="external text" href="https://dl.acm.org/doi/10.1145/366622.366647">"Algorithm 65: find"</a>. Communications of the ACM. 4 (7): 321–322. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F366622.366647">10.1145/366622.366647</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0001-0782">0001-0782</a>.</cite>

</li>

<li id="cite_note-6"><a href="#cite_ref-6">^</a> <cite id="CITEREFBlumFloydPrattRivest1973" class="citation journal cs1">Blum, Manuel; Floyd, Robert W.; Pratt, Vaughan; Rivest, Ronald L.; Tarjan, Robert E. (August 1973). <a rel="nofollow" class="external text" href="https://linkinghub.elsevier.com/retrieve/pii/S0022000073800339">"Time bounds for selection"</a>. Journal of Computer and System Sciences. 7 (4): 448–461. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0022-0000%2873%2980033-9">10.1016/S0022-0000(73)80033-9</a>.</cite>

</li>

<li id="cite_note-7"><a href="#cite_ref-7">^</a> <cite id="CITEREFWilliamsShallit1994" class="citation cs2"><a href="Hugh_C._Williams" title="Hugh C. Williams">Williams, H. C.</a>; <a href="Jeffrey_Shallit" title="Jeffrey Shallit">Shallit, J. O.</a> (1994), "Factoring integers before computers", in Gautschi, Walter (ed.), Mathematics of Computation 1943–1993: a half-century of computational mathematics; Papers from the Symposium on Numerical Analysis and the Minisymposium on Computational Number Theory held in Vancouver, British Columbia, August 9–13, 1993, Proceedings of Symposia in Applied Mathematics, vol. 48, Amer. Math. Soc., Providence, RI, pp. 481–531, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1090%2Fpsapm%2F048%2F1314885">10.1090/psapm/048/1314885</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-8218-0291-5</bdi>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1314885">1314885</a></cite>; see p. 504, "Perhaps Pocklington also deserves credit as the inventor of the randomized algorithm".

</li>

<li id="cite_note-8"><a href="#cite_ref-8">^</a> <cite id="CITEREFBerlekamp1971" class="citation book cs1">Berlekamp, E. R. (1971). <a rel="nofollow" class="external text" href="http://portal.acm.org/citation.cfm?doid=800204.806290">"Factoring polynomials over large finite fields"</a>. Proceedings of the second ACM symposium on Symbolic and algebraic manipulation - SYMSAC '71. Los Angeles, California, United States: ACM Press. p. 223. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F800204.806290">10.1145/800204.806290</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9781450377867</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:6464612">6464612</a>.</cite>

</li>

<li id="cite_note-:0-9">^ <a href="#cite_ref-:0_9-0">a</a> <a href="#cite_ref-:0_9-1">b</a> <a href="#cite_ref-:0_9-2">c</a> <a href="#cite_ref-:0_9-3">d</a> <a href="#cite_ref-:0_9-4">e</a> <a href="#cite_ref-:0_9-5">f</a> <cite id="CITEREFKnuth1998" class="citation book cs1">Knuth, Donald E. (1998). <a rel="nofollow" class="external text" href="https://dl.acm.org/doi/10.5555/280635">The art of computer programming, volume 3: (2nd ed.) sorting and searching</a>. USA: Addison Wesley Longman Publishing Co., Inc. pp. 536–549. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-201-89685-5</bdi>.</cite>

</li>

<li id="cite_note-10"><a href="#cite_ref-10">^</a> <a href="Donald_Knuth" title="Donald Knuth">Knuth, Donald</a> (1963), <a rel="nofollow" class="external text" href="https://web.archive.org/web/20160303225949/http://algo.inria.fr/AofA/Research/11-97.html">Notes on "Open" Addressing</a>, archived from the original on 2016-03-03

</li>

<li id="cite_note-11"><a href="#cite_ref-11">^</a> <cite id="CITEREFKonheimWeiss1966" class="citation journal cs1">Konheim, Alan G.; Weiss, Benjamin (November 1966). <a rel="nofollow" class="external text" href="https://dx.doi.org/10.1137/0114101">"An Occupancy Discipline and Applications"</a>. SIAM Journal on Applied Mathematics. 14 (6): 1266–1274. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F0114101">10.1137/0114101</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0036-1399">0036-1399</a>.</cite>

</li>

<li id="cite_note-12"><a href="#cite_ref-12">^</a> <cite id="CITEREFCarterWegman1979" class="citation journal cs1">Carter, J. Lawrence; Wegman, Mark N. (1979-04-01). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0022-0000%2879%2990044-8">"Universal classes of hash functions"</a>. Journal of Computer and System Sciences. 18 (2): 143–154. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0022-0000%2879%2990044-8">10.1016/0022-0000(79)90044-8</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0022-0000">0022-0000</a>.</cite>

</li>

<li id="cite_note-13"><a href="#cite_ref-13">^</a> <cite id="CITEREFBloom1970" class="citation journal cs1">Bloom, Burton H. (July 1970). <a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F362686.362692">"Space/time trade-offs in hash coding with allowable errors"</a>. Communications of the ACM. 13 (7): 422–426. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F362686.362692">10.1145/362686.362692</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0001-0782">0001-0782</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:7931252">7931252</a>.</cite>

</li>

<li id="cite_note-14"><a href="#cite_ref-14">^</a> <cite id="CITEREFAragonSeidel1989" class="citation book cs1">Aragon, C.R.; Seidel, R.G. (October 1989). "Randomized search trees". 30th Annual Symposium on Foundations of Computer Science. pp. 540–545. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FSFCS.1989.63531">10.1109/SFCS.1989.63531</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-8186-1982-1</bdi>.</cite>

</li>

<li id="cite_note-15"><a href="#cite_ref-15">^</a> <a href="William_Pugh_(computer_scientist)" title="William Pugh (computer scientist)">Pugh, William</a> (April 1989). <a rel="nofollow" class="external text" href="http://drum.lib.umd.edu/handle/1903/542">Concurrent Maintenance of Skip Lists</a> (PS, PDF) (Technical report). Dept. of Computer Science, U. Maryland. CS-TR-2222.

</li>

<li id="cite_note-:1-16">^ <a href="#cite_ref-:1_16-0">a</a> <a href="#cite_ref-:1_16-1">b</a> <cite id="CITEREFAlonSpencer2016" class="citation book cs1">Alon, Noga; Spencer, Joel H. (2016). The probabilistic method (Fourth ed.). Hoboken, New Jersey: Wiley. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-119-06195-3</bdi>. <a href="OCLC_(identifier)" class="mw-redirect" title="OCLC (identifier)">OCLC</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/oclc/910535517">910535517</a>.</cite>

</li>

<li id="cite_note-17"><a href="#cite_ref-17">^</a> P. Erdős: Some remarks on the theory of graphs, Bull. Amer. Math. Soc. 53 (1947), 292--294 MR8,479d; Zentralblatt 32,192.

</li>

<li id="cite_note-18"><a href="#cite_ref-18">^</a> <cite id="CITEREFErdös1959" class="citation journal cs1">Erdös, P. (1959). <a rel="nofollow" class="external text" href="https://doi.org/10.4153%2FCJM-1959-003-9">"Graph Theory and Probability"</a>. Canadian Journal of Mathematics. 11: 34–38. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.4153%2FCJM-1959-003-9">10.4153/CJM-1959-003-9</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0008-414X">0008-414X</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:122784453">122784453</a>.</cite>

</li>

<li id="cite_note-19"><a href="#cite_ref-19">^</a> Seidel R. <a rel="nofollow" class="external text" href="http://www.cs.berkeley.edu/~jrs/meshpapers/Seidel.ps.gz">Backwards Analysis of Randomized Geometric Algorithms</a>.

</li>

<li id="cite_note-20"><a href="#cite_ref-20">^</a> <cite id="CITEREFKarger1999" class="citation journal cs1">Karger, David R. (1999). "Random Sampling in Cut, Flow, and Network Design Problems". <a href="Mathematics_of_Operations_Research" title="Mathematics of Operations Research">Mathematics of Operations Research</a>. 24 (2): 383–413. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.215.794">10.1.1.215.794</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1287%2Fmoor.24.2.383">10.1287/moor.24.2.383</a>.</cite>

</li>

<li id="cite_note-21"><a href="#cite_ref-21">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://ocw.mit.edu/courses/6-046j-design-and-analysis-of-algorithms-spring-2012/resources/mit6_046js12_lec22/">"6.046J Lecture 22: Derandomization | Design and Analysis of Algorithms | Electrical Engineering and Computer Science"</a>. MIT OpenCourseWare. Retrieved 2024-12-27.</cite>

</li>

<li id="cite_note-22"><a href="#cite_ref-22">^</a> <cite id="CITEREFLubyWigderson1995" class="citation report cs1">Luby, Michael; Wigderson, Avi (July 1995). <a rel="nofollow" class="external text" href="https://dl.acm.org/doi/10.5555/894682">Pairwise Independence and Derandomization</a> (Report). USA: University of California at Berkeley.</cite>

</li>

<li id="cite_note-:2-23">^ <a href="#cite_ref-:2_23-0">a</a> <a href="#cite_ref-:2_23-1">b</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://people.seas.harvard.edu/~salil/cs225/spring09/lecnotes/list.htm">"Lecture Notes, Chapter 3. Basic Derandomization Techniques"</a>. people.seas.harvard.edu. Retrieved 2024-12-27.</cite>

</li>

<li id="cite_note-24"><a href="#cite_ref-24">^</a> <cite id="CITEREFChazelleFriedman1990" class="citation journal cs1">Chazelle, B.; Friedman, J. (1990-09-01). <a rel="nofollow" class="external text" href="https://doi.org/10.1007/BF02122778">"A deterministic view of random sampling and its use in geometry"</a>. Combinatorica. 10 (3): 229–249. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF02122778">10.1007/BF02122778</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1439-6912">1439-6912</a>.</cite>

</li>

<li id="cite_note-25"><a href="#cite_ref-25">^</a> <cite id="CITEREFAlippi2014" class="citation cs2">Alippi, Cesare (2014), Intelligence for Embedded Systems, Springer, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-319-05278-6</bdi></cite>.

</li>

<li id="cite_note-26"><a href="#cite_ref-26">^</a> <cite id="CITEREFKushilevitzNisan2006" class="citation cs2">Kushilevitz, Eyal; Nisan, Noam (2006), Communication Complexity, Cambridge University Press, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9780521029834</bdi></cite>. For the deterministic lower bound see p. 11; for the logarithmic randomized upper bound see pp. 31–32.

</li>

<li id="cite_note-27"><a href="#cite_ref-27">^</a> <cite id="CITEREFDyerFriezeKannan1991" class="citation cs2">Dyer, M.; Frieze, A.; Kannan, R. (1991), <a rel="nofollow" class="external text" href="http://www.math.cmu.edu/~af1p/Texfiles/oldvolume.pdf">"A random polynomial-time algorithm for approximating the volume of convex bodies"</a> (PDF), <a href="Journal_of_the_ACM" title="Journal of the ACM">Journal of the ACM</a>, 38 (1): 1–17, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F102782.102783">10.1145/102782.102783</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:13268711">13268711</a></cite>

</li>

<li id="cite_note-28"><a href="#cite_ref-28">^</a> <cite id="CITEREFFürediBárány1986" class="citation cs2"><a href="Zolt%C3%A1n_F%C3%BCredi" title="Zoltán Füredi">Füredi, Z.</a>; Bárány, I. (1986), "Computing the volume is difficult", <a rel="nofollow" class="external text" href="https://ecommons.cornell.edu/bitstream/1813/8572/1/TR000688.pdf">Proc. 18th ACM Symposium on Theory of Computing (Berkeley, California, May 28–30, 1986)</a> (PDF), New York, NY: ACM, pp. 442–447, <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.726.9448">10.1.1.726.9448</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F12130.12176">10.1145/12130.12176</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-89791-193-8</bdi>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:17867291">17867291</a></cite>

</li>

<li id="cite_note-29"><a href="#cite_ref-29">^</a> <cite id="CITEREFShamir1992" class="citation cs2"><a href="Adi_Shamir" title="Adi Shamir">Shamir, A.</a> (1992), "IP = PSPACE", Journal of the ACM, 39 (4): 869–877, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F146585.146609">10.1145/146585.146609</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:315182">315182</a></cite>

</li>

<li id="cite_note-30"><a href="#cite_ref-30">^</a> <cite id="CITEREFCookSoloveichikWinfreeBruck2009" class="citation cs2"><a href="Matthew_Cook" title="Matthew Cook">Cook, Matthew</a>; Soloveichik, David; <a href="Erik_Winfree" title="Erik Winfree">Winfree, Erik</a>; Bruck, Jehoshua (2009), "Programmability of chemical reaction networks", in <a href="Anne_Condon" title="Anne Condon">Condon, Anne</a>; <a href="David_Harel" title="David Harel">Harel, David</a>; Kok, Joost N.; <a href="Arto_Salomaa" title="Arto Salomaa">Salomaa, Arto</a>; <a href="Erik_Winfree" title="Erik Winfree">Winfree, Erik</a> (eds.), <a rel="nofollow" class="external text" href="https://authors.library.caltech.edu/26121/1/etr090.pdf">Algorithmic Bioprocesses</a> (PDF), Natural Computing Series, Springer-Verlag, pp. 543–584, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-540-88869-7_27">10.1007/978-3-540-88869-7_27</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-88868-0</bdi></cite>.

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

<ul><li><a href="Thomas_H._Cormen" title="Thomas H. Cormen">Thomas H. Cormen</a>, <a href="Charles_E._Leiserson" title="Charles E. Leiserson">Charles E. Leiserson</a>, <a href="Ronald_L._Rivest" class="mw-redirect" title="Ronald L. Rivest">Ronald L. Rivest</a>, and <a href="Clifford_Stein" title="Clifford Stein">Clifford Stein</a>. <a href="Introduction_to_Algorithms" title="Introduction to Algorithms">Introduction to Algorithms</a>, Second Edition. MIT Press and McGraw–Hill, 1990. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-262-03293-7</bdi>. Chapter 5: Probabilistic Analysis and Randomized Algorithms, pp. 91–122.</li>

<li>Dirk Draheim. <a rel="nofollow" class="external text" href="https://www.springer.com/de/book/9783642551970">"Semantics of the Probabilistic Typed Lambda Calculus (Markov Chain Semantics, Termination Behavior, and Denotational Semantics)."</a> Springer, 2017.</li>

<li><a href="Jon_Kleinberg" title="Jon Kleinberg">Jon Kleinberg</a> and <a href="%C3%89va_Tardos" title="Éva Tardos">Éva Tardos</a>. Algorithm Design. Chapter 13: "Randomized algorithms".</li>

<li><cite id="CITEREFFallis2000" class="citation journal cs1">Fallis, D. (2000). "The reliability of randomized algorithms". The British Journal for the Philosophy of Science. 51 (2): 255–271. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1093%2Fbjps%2F51.2.255">10.1093/bjps/51.2.255</a>.</cite></li>

<li><a href="Michael_Mitzenmacher" title="Michael Mitzenmacher">M. Mitzenmacher</a> and <a href="Eli_Upfal" title="Eli Upfal">E. Upfal</a>. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, New York (NY), 2005.</li>

<li><a href="Rajeev_Motwani" title="Rajeev Motwani">Rajeev Motwani</a> and P. Raghavan. Randomized Algorithms. Cambridge University Press, New York (NY), 1995.</li>

<li>Rajeev Motwani and P. Raghavan. <a rel="nofollow" class="external text" href="http://portal.acm.org/citation.cfm?id=234313.234327">Randomized Algorithms</a>. A survey on Randomized Algorithms.</li>

<li><cite id="CITEREFChristos_Papadimitriou1993" class="citation cs2"><a href="Christos_Papadimitriou" title="Christos Papadimitriou">Christos Papadimitriou</a> (1993), Computational Complexity (1st ed.), Addison Wesley, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-201-53082-7</bdi></cite> Chapter 11: Randomized computation, pp. 241–278.</li>

<li><cite id="CITEREFRabin1980" class="citation journal cs1">Rabin, Michael O. (1980). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0022-314X%2880%2990084-0">"Probabilistic algorithm for testing primality"</a>. Journal of Number Theory. 12: 128–138. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0022-314X%2880%2990084-0">10.1016/0022-314X(80)90084-0</a>.</cite></li>

<li>A. A. Tsay, W. S. Lovejoy, David R. Karger, Random Sampling in Cut, Flow, and Network Design Problems, Mathematics of Operations Research, 24(2):383–413, 1999.</li>

<li><a rel="nofollow" class="external text" href="https://www.osti.gov/biblio/1807223">"Randomized Algorithms for Scientific Computing" (RASC), OSTI.GOV (July 10th, 2021).</a></li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Data_structures_and_algorithms145" style="padding:3px"><table class="nowraplinks hlist mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Data_structures_and_algorithms145" style="font-size:114%;margin:0 4em"><a href="Data_structure" title="Data structure">Data structures</a> and <a href="Algorithm" title="Algorithm">algorithms</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">Data structures</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Array_(data_structure)" title="Array (data structure)">Array</a></li>

<li><a href="Associative_array" title="Associative array">Associative array</a></li>

<li><a href="Binary_search_tree" title="Binary search tree">Binary search tree</a></li>

<li><a href="Fenwick_tree" title="Fenwick tree">Fenwick tree</a></li>

<li><a href="Graph_(abstract_data_type)" title="Graph (abstract data type)">Graph</a></li>

<li><a href="Hash_table" title="Hash table">Hash table</a></li>

<li><a href="Linked_list" title="Linked list">Linked list</a></li>

<li><a href="Queue_(abstract_data_type)" title="Queue (abstract data type)">Queue</a></li>

<li><a href="Segment_tree" title="Segment tree">Segment tree</a></li>

<li><a href="Stack_(abstract_data_type)" title="Stack (abstract data type)">Stack</a></li>

<li><a href="String_(computer_science)" title="String (computer science)">String</a></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Algorithms and <a href="Algorithmic_paradigm" title="Algorithmic paradigm">algorithmic paradigms</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Backtracking" title="Backtracking">Backtracking</a></li>

<li><a href="Binary_search" title="Binary search">Binary search</a></li>

<li><a href="Breadth-first_search" title="Breadth-first search">Breadth-first search</a></li>

<li><a href="Brute-force_search" title="Brute-force search">Brute-force search</a></li>

<li><a href="Depth-first_search" title="Depth-first search">Depth-first search</a></li>

<li><a href="Divide-and-conquer_algorithm" title="Divide-and-conquer algorithm">Divide and conquer</a></li>

<li><a href="Dynamic_programming" title="Dynamic programming">Dynamic programming</a></li>

<li><a href="Graph_traversal" title="Graph traversal">Graph traversal</a></li>

<li><a href="Greedy_algorithm" title="Greedy algorithm">Greedy</a></li>

<li><a href="Hash_function" title="Hash function">Hash function</a></li>

<li><a href="Minimax" title="Minimax">Minimax</a></li>

<li><a href="Online_algorithm" title="Online algorithm">Online</a></li>

<li><a href="Recursion_(computer_science)" title="Recursion (computer science)">Recursion</a></li>

<li><a href="Root-finding_algorithm" title="Root-finding algorithm">Root-finding</a></li>

<li><a href="Sorting_algorithm" title="Sorting algorithm">Sorting</a></li>

<li><a href="Streaming_algorithm" title="Streaming algorithm">Streaming</a></li>

<li><a href="Sweep_line_algorithm" title="Sweep line algorithm">Sweep line</a></li>

<li><a href="String-searching_algorithm" title="String-searching algorithm">String-searching</a></li>

<li><a href="Topological_sorting" title="Topological sorting">Topological sorting</a></li></ul>

</div></td></tr><tr><td class="navbox-abovebelow" colspan="2"><div>

<ul><li><a href="List_of_data_structures" title="List of data structures">List of data structures</a></li>

<li><a href="List_of_algorithms" title="List of algorithms">List of algorithms</a></li></ul>

</div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-08-05" href="https://en.wikipedia.org/wiki/?title=Randomized_algorithm&oldid=1304365839">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>